# 层序遍历 迭代解法
from pythonds import BinaryTree;
from collections import deque;
def levelOrder(root):
    results=[]
    if not root:
        return results;
    que=deque([root])

    while que:
        size=len(que)
        result=[]
        for _ in range(size):
            cur=que.popleft(); # 移去并且返回一个元素，deque 最左侧的那一个。 如果没有元素的话，就引发 IndexError。
            result.append(cur.key);
            if cur.getLeftChild():
                que.append(cur.getLeftChild())
            if cur.getRightChild():
                que.append(cur.getRightChild())
        results.append(result)
    return results
root=BinaryTree('A')
root.insertLeft('B')
root_left=root.getLeftChild()
root_left.insertLeft("D")
root_left.insertRight("E")
root_left_right=root_left.getRightChild()
root_left_right.insertRight("J")
root.insertRight("C")
root_right=root.getRightChild()
root_right.insertLeft("F")
root_right_left=root_right.getLeftChild()
root_right_left.insertRight("I")
root_right.insertRight("G")
print("层序遍历:",levelOrder(root))
